package lanqiao.真题.第13届决赛JavaB组;

import java.util.*;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 这天，小明在玩迷宫游戏。迷宫为一个n×n的网格图，小明可以在格子中移动，左上角为(1,1)，右下角(n，n)为终点。
 * 迷宫中除了可以向上左右四个方向移动一格以外，还有个双向传送门可以使用，传送门可以连接两个任意格子。
 * 假如小明处在格子(x1,y1),同时有一个传送门连接了格子(x1，y1)和
 * (x2,y2),那么小明既可以花费1的步数向上下左右四个方向之一走一格（不能越过边界)，
 * 也可以花费1的步数通过传送门走到格子(x2,y2)去。
 * 而对于同一个迷宫，小明每次进入的初始格子是在这n×n个格子中均匀随
 * 机的（当然运气好可以直接随机到终点），他想知道从初始格子走到终点的最短步数的期望值是多少。
 * <p>
 * 【输入格式】
 * 输入共1+m行，第一行为两个正整数n,m。
 * 后面m行，每行四个正整数x1,y1,x2,y2表示第i个传送门连接的两个格子坐标。
 * 【输出格式】
 * 输出共一行，一个浮点数表示答案（请保留两位小数）。
 * 【样例输入】
 * 2	1
 * 1	1	2	2
 * <p>
 * 【样例输出】
 * 0.75
 * 【样例解释】
 * 由于传送门的存在，从(1,1)出发到终点(2,2)只需要一步：而从(1,2)和
 * (2,1)出发也只需要向下/右走一步：从(2,2)出发需要0步。所以步数期望为1+1+1+0 / 2×2 =0.75。
 * <p>
 * 【评测用例规模与约定】
 * 对于20%的数据，保证n,m≤20。
 * 对于100%的数据，保证n,m≤2000。x1,y1,x2,y2≤n。
 * @since 2023-05-29 22:36
 */
public class E_迷宫 {
}

class MainE {
    static int n, m;
    static int x1, y1, x2, y2;
    //传送门: 起始位置(i*行数+j) -> 结束位置(i,j)
    //考虑当期位置有多个传送门
    static Map<Integer, List<int[]>> map = new HashMap<>();
    //记录当期位置是否达到
    static boolean[][] vis;
    //四个方向
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        vis = new boolean[n][n];
        m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            x1 = sc.nextInt() - 1;
            y1 = sc.nextInt() - 1;
            x2 = sc.nextInt() - 1;
            y2 = sc.nextInt() - 1;
            //保存传送门信息
            build(x1, y1, x2, y2);
            build(x2, y2, x1, y1);
        }
        /*
        从终点开始bfs
        到达的点需要的步数是最少的
         */
        bfs(n - 1, n - 1);
    }

    static void bfs(int x, int y) {
        Deque<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        vis[x][y] = true;
        int i, j;
        //步数
        int step = 0;
        //累加步数
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] cur = queue.poll();
                i = cur[0];
                j = cur[1];
                ans += step;
                //传送门
                if (map.containsKey(i * n + j)) {
                    for (int[] next : map.get(i * n + j)) {
                        if (!vis[next[0]][next[1]]) {
                            vis[next[0]][next[1]] = true;
                            queue.offer(new int[]{next[0], next[1]});
                        }
                    }
                }
                //四个方向
                for (int[] dir : dirs) {
                    int nextX = i + dir[0];
                    int nextY = j + dir[1];
                    if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && !vis[nextX][nextY]) {
                        vis[nextX][nextY] = true;
                        queue.offer(new int[]{nextX, nextY});
                    }
                }
            }
            step++;
        }
        System.out.printf("%.2f", ans * 1.0 / (n * n));
    }

    private static void build(int x1, int y1, int x2, int y2) {
        if (!map.containsKey(x1 * n + y1)) {
            map.put(x1 * n + y1, new ArrayList<>());
        }
        map.get(x1 * n + y1).add(new int[]{x2, y2});
    }
}

